package com.kyle.java.recursive;

/**
 * @author kyle
 * @version 1.0
 * @date 2021/4/3 22:04
 * <p>
 * 运用递归思想解决迷宫问题
 * <p>
 * 二维数组为迷宫，大小为4x4
 * 未走过的路径表示 0
 * 障碍表示为1
 * 走过的路径为2
 * 起点为3
 * 终点为4
 */
public class Maze {
    public static void main(String[] args) {
        int[][] maze = {{1, 1, 1, 1, 1, 1}, {1, 3, 0, 1, 0, 1}, {1, 0, 1, 0, 0, 1}, {1, 0, 0, 1, 0, 1}, {1, 1, 0, 0, 4, 1}, {1, 1, 1, 1, 1, 1}};
        for (int i = 0; i < maze.length; i++) {
            System.out.println();
            for (int j = 0; j < maze[0].length; j++) {
                System.out.print(maze[i][j]);
            }
        }
        moveToTheGoal(maze, 1, 1);
        for (int i = 0; i < maze.length; i++) {
            System.out.println();
            for (int j = 0; j < maze[0].length; j++) {
                System.out.print(maze[i][j]);
            }
        }
    }

    public static boolean moveToTheGoal(int[][] maze, int i, int j) {
        if (maze[i][j] == 4) {//当前的点是终点
            System.out.println("找到了");
            return true;
        } else if (maze[i][j] == 0 || maze[i][j] == 3) { //当前出发的点是起点或者是可通路径
            maze[i][j] = 2;                 //假定自己走对了，继续按  上、右、下、左顺序走
            if (moveToTheGoal(maze, i - 1, j)) {  //尝试往上走，如果走通了,返回true
                return true;
            }
            if (moveToTheGoal(maze, i , j+1)) {  //尝试往右走，如果走通了,返回true
                return true;
            }
            if (moveToTheGoal(maze, i +1, j)) {  //尝试往下走，如果走通了,返回true
                return true;
            }
            if (moveToTheGoal(maze, i , j-1)) {  //尝试往左走，如果走通了,返回true
                return true;
            } else {
                maze[i][j] = 0; //回溯
                return false;
            }
        } else { //当前的点是1（障碍) 或者 回溯到2了
            return false;
        }

    }



}
